package com.company;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Stack;

/**
 * 1047. 删除字符串中的所有相邻重复项
 * 给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
 *
 * 在 S 上反复执行重复项删除操作，直到无法继续删除。
 *
 * 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution1047 {
    /**
     * 使用栈来进行删除，效率过慢
     * @param args
     */
    /*public static String removeDuplicates(String s) {
        Deque<Character> stack=new ArrayDeque<>();
        for (char c:s.toCharArray())
        {
            if(stack.isEmpty())
            {
                stack.push(c);
            }else if (stack.peek()==c)
            {
                stack.pop();
            }else
            {
                stack.push(c);
            }
        }
        String s1="";
        while(!stack.isEmpty())
        {
            s1=stack.pop()+s1;
        }
        return s1;
    }*/

    /**
     * 使用指针在原字符串中操作，效率翻倍
     * @param s
     * @return
     */
    public static String removeDuplicates(String s){
        char[] chars=s.toCharArray();
        int top=-1;
        for (int i=0;i<chars.length;i++)
        {
            if(top==-1||chars[top]!=chars[i])
            {
                chars[++top]=chars[i];
            }else
            {
                top--;
            }
        }
        return String.valueOf(chars,0,top+1);
    }


    public static void main(String[] args) {
        System.out.println(removeDuplicates("abbaca"));
    }
}
